package 剑指offer;

import java.util.ArrayList;
import java.util.List;

/**
 * @author zhangmin
 * @create 2021-12-05 17:30
 * 数学
 */
public class day24_141_572_62 {

    /**==============================================================================================================================================
     * 剑指 Offer 14- I. 剪绳子
     * 给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]...k[m-1] 。请问 k[0]*k[1]*...*k[m-1] 可能的最大乘积是多少？
     * 1、数学：算术几何不等式：推论一： 将绳子 以相等的长度等分为多段 ，得到的乘积最大。
     *                       推论二： 尽可能将绳子以长度 3 等分为多段时，乘积最大。
     *         流程：当 n≤3 时，按照规则应不切分，但由于题目要求必须剪成 m>1 段，因此必须剪出一段长度为 1 的绳子，即返回 n - 1 。
     *         当 n>3 时，求 n 除以 3 的 整数部分 a 和 余数部分 b （即 n = 3a + b ），并分为以下三种情况
     *         当 b = 0 时，直接返回 3^a
     *         当 b = 1 时，要将一个 1 + 3转换为 2+2，因此返回 3^{a-1}*4
     *         当 b = 2 时，返回 3^a *2
     * 2、贪心
     * */
    public int cuttingRope(int n) {
        if(n<=3) return n-1;
        int a=n/3,b=n%3;
        if (b==0) return (int) Math.pow(3,a);
        if (b==1) return (int) (Math.pow(3,a-1)*4);
        return (int) (Math.pow(3,a)*2);
    }

    /**==============================================================================================================================================
     * 剑指 Offer 57 - II. 和为s的连续正数序列
     * 输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。
     * 双指针： l 和 r 表示当前枚举到的以 l 为起点到 r 的区间，sum 表示 [l,r] 的区间和，由求和公式可sum=((l+r)*(r-l+1))/2
     *      如果 sum<target 则说明指针 r 还可以向右拓展使得 sum 增大，此时指针 r 向右移动，即 r+=1
     *      如果 sum>target 则说明以 l 为起点不存在一个 r 使得 sum=target ，此时要枚举下一个起点，指针 l 向右移动，即l+=1
     *      如果 sum==target 则说明我们找到了以 l 为起点得合法解 [l,r]，我们需要将 [l,r] 的序列放进答案数组，且我们知道以 l为起点的合法解最多只有一个，所以需要枚举下一个起点，指针 l 向右移动，即 l+=1
     * */
    public int[][] findContinuousSequence(int target) {
        List<int[]> res=new ArrayList<>();
        int l=1,r=2;
        while (l<r){
            int sum=((l+r)*(r-l+1))/2;
            if (sum==target){
                //将从[l,r]加入结果中
                int[] resi=new int[r-l+1];
                for (int i = l; i <=r ; i++) {
                    //从下标0开始存储
                    resi[i-l]=i;
                }
                res.add(resi);
                l++;
            }else if (sum<target){
                r++;
            }else {
                l++;
            }
        }
        return res.toArray(new int[res.size()][]);
    }

    /**==============================================================================================================================================
     * 剑指 Offer 62. 圆圈中最后剩下的数字
     * 0,1,···,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字（删除后从下一个数字开始计数）。求出这个圆圈里剩下的最后一个数字。
     * */
    public int lastRemaining(int n, int m) {
        int f=0;
        for (int i = 2; i !=n+1 ; i++) {
            f=(f+m)%i;
        }
        return f;
    }
}
